package org.example.two.datatype;

/**
 * 抽象数据类型--优先队列
 * @param <Key>
 */
public class MaxPQ<Key extends Comparable<Key>>{
    // 定义一个数组，用于存储元素
    private Key[] pq;

    // 定义一个变量，用于存储数组中的元素个数
    private int N = 0;
    // 构造函数，用于初始化最大堆
    public MaxPQ(int maxN){
        pq = (Key[]) new Comparable[maxN+1];
    }

    // 构造函数，用于初始化最大堆
    public MaxPQ(Key[] pq) {
        this.pq = pq;
    }

    // 判断最大堆是否为空
    public boolean isEmpty(){
        return N==0;
    }
    // 返回最大堆的大小
    public int size(){
        return N;
    }

    // 向最大堆中插入一个元素
    public void insert(Key v){
        pq[++N] = v;
        // 将插入的元素上浮到最大堆的位置
        swim(N);
    }
    // 从最大堆中删除最大元素
    public Key delMax(){
        Key max = pq[1];
        // 与堆的最后一个元素交换，然后下沉到合适的位置
        exch(1,N--);
        pq[N+1] = null;
        sink(1);
        return max;
    }
    // 比较两个元素的大小
    private boolean less(int i , int j){
        return pq[i].compareTo(pq[j])<0;
    }
    // 交换两个元素的位置
    private void exch(int i ,int j){
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
    // 将元素上浮到最大堆的位置
    private void swim(int k){
        // 如果当前元素大于其父元素，则交换它们的位置，然后继续上浮
        while (k != 1 && less(k/2,k)){
            exch(k/2,k);
            k=k/2;
        }
    }
    // 将元素下沉到合适的位置
    private void sink(int k){
        // 如果当前元素有子元素，并且当前元素小于子元素中的较大者，则交换它们的位置，然后继续下沉
        while (k*2<N){
            int j=k*2;
            if (less(j,j+1)){
                j++;
            }
            if (!less(k,j)){
                break;
            }
            exch(k,j);
            k=j;
        }
    }



}
